import java.io.*;
import java.util.*;
import java.math.*;

class nQueens
{
	public static int board[] = new int[20];
	public static int count = 0;
	
	public static void main (String[] args) 
	{
		int n = getInt();
		queen(1,n);		
	}
	
 	static void queen(int row, int n)
 	{
 		for(int column=1;column<=n;column++)
 		{
 			if(place(row,column))
 			{
 				board[row]=column;
 				
 				if(row==n)
 					print_board(n);
 				else
 					queen(row+1,n);
 			}
 		}
 	}
 	
 	static boolean place(int row, int column)
 	{
 		for(int i=1;i<=(row-1);i++)
 		{
 			if(board[i]==column)
 				return false;
 			if(Math.abs(board[i]-column)==Math.abs(i-row))
 				return false;
 		}
 		return true;
 	}
 	
 	static void print_board(int n)
 	{
 		int i, j;
	System.out.print("\n \n \n Solution: "+(++count));
	System.out.print(" \n \n ");
	for(i=1;i<=n;i++)
	{
		System.out.print("\t "+i);
	}
	for(i=1;i<=n;i++)
	{
		System.out.print("\n \n "+i);
		for(j=1;j<=n;j++)
		{
			if(board[i]==j)
				System.out.print("\t Q");
			else
				System.out.print("\t *");
		}
	}
 	}
	
	static int getInt()
	{
		Scanner k = new Scanner(System.in);
		
		System.out.print("\n Enter the number of Queens : ");
		int n = k.nextInt();
		return n;
	}
	
}